package month202011;

/**
 *  手写一个双向循环链表；
 */
public class MyCircularDeque {

    class DoudleCircularLinkedNode{
        private int value;
        private DoudleCircularLinkedNode prev;
        private DoudleCircularLinkedNode next;

        public DoudleCircularLinkedNode() {
        }
        public DoudleCircularLinkedNode(int value){
            this.value = value;
        }
    }

    /**
     * 成员变量
     * 1、capacity 容量大小
     * 2、size 当前大小
     * 3、伪头节点
     */
    private int capacity;
    private int size;
    private DoudleCircularLinkedNode head;

    /** Initialize your data structure here. Set the size of the deque to be k. */
    public MyCircularDeque(int k) {
        this.capacity = k;
        this.size = 0;
        this.head = new DoudleCircularLinkedNode();
        head.prev = head;
        head.next = head;

    }

    /**
     *      3 <=>2 <=> 1 <=>head <=> 3
     *                  ↓
     *      3 <=>2 <=> 1 <=> 0 <=>head <=> 3
     *
     *      0.prev = head
     *      0.next = 1 (head.next)
     *      1.prev = 0
     *      head.next = 0
     */
    /** Adds an item at the front of Deque. Return true if the operation is successful. */
    public boolean insertFront(int value) {
        if(size >= capacity){
            return false;
        }
        DoudleCircularLinkedNode newNode = new DoudleCircularLinkedNode(value);
        newNode.prev =head;
        newNode.next = head.next;
        head.next.prev = newNode;
        head.next = newNode;
        size++;
        return true;
    }


    /**
     *      3 <=>2 <=> 1 <=>head <=> 3
     *                  ↓
     *      4 <=>3 <=>2 <=> 1 <=>head <=> 4
     *
     *      4.prev = 3 (head.prev)
     *      4.next = head
     *      3.next = 4
     *      head.prev = 4
     */
    /** Adds an item at the rear of Deque. Return true if the operation is successful. */
    public boolean insertLast(int value) {
        if(size >= capacity){
            return false;
        }
        DoudleCircularLinkedNode newNode = new DoudleCircularLinkedNode(value);
        newNode.prev = head.prev;
        newNode.next = head;
        head.prev.next = newNode;
        head.prev = newNode;
        size++;
        return true;
    }

    /**
     *
     * 3 <=>2 <=> 1 <=> 0 <=>head <=> 3
     *                  ↓
     *       3 <=>2 <=> 1 <=>head <=> 3
     *
     *      head.next.next.prev = head; // 1 -> head
     *      head.next = head.next.next; // head -> 1
     *
     */
    /** Deletes an item from the front of Deque. Return true if the operation is successful. */
    public boolean deleteFront() {
        if(size <= 0){
            return false;
        }
        head.next.next.prev = head;
        head.next = head.next.next;
        size--;
        return true;
    }


    /**
     * 4 <=>3 <=>2 <=> 1 <=>head <=> 4
     *                 ↓
     *      3 <=>2 <=> 1 <=>head <=> 3
     *
     *      head.prev.prev.next = head; // 3 -> head
     *      head.prev = head.prev.prev; // head -> 3
     *
     */
    /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
    public boolean deleteLast() {
        if(size <= 0){
            return false;
        }
        head.prev.prev.next = head;
        head.prev = head.prev.prev;
        size--;
        return true;
    }

    /**
     *  3 <=>2 <=> 1 <=>head <=> 3
     *      return 1;
     */
    /** Get the front item from the deque. */
    public int getFront() {
        if(size <= 0){
            return -1;
        }
        return head.next.value;
    }

    /**
     *  3 <=>2 <=> 1 <=>head <=> 3
     *      return 3;
     */
    /** Get the last item from the deque. */
    public int getRear() {
        if(size <= 0){
            return -1;
        }
        return head.prev.value;
    }

    /** Checks whether the circular deque is empty or not. */
    public boolean isEmpty() {
        return size == 0;

    }

    /** Checks whether the circular deque is full or not. */
    public boolean isFull() {
        return size == capacity;

    }
}
